/*
题目: 可被三整除的最大和
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

https://leetcode.cn/problems/greatest-sum-divisible-by-three/
 */
public class MaxSumDivThree {
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        // 表示 余数 为 k 时的最大值
        int[] dp = new int[3];

        for (int i = 0; i < n; i ++) {
            int a = dp[0] + nums[i];
            int b = dp[1] + nums[i];
            int c = dp[2] + nums[i];
            dp[a % 3] = Math.max(dp[a % 3], a);
            dp[b % 3] = Math.max(dp[b % 3], b);
            dp[c % 3] = Math.max(dp[c % 3], c);
        }
        return dp[0];
    }
}
